﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200915
    {
        int[] dp;
        /// <summary>
        /// 最大上升子序列
        /// dp[i] :以第i个数为末尾的最大上述子序列
        /// dp[i]=max{1，dp[j]+1 j<i&a[j-1]<a[i-1]}
        /// </summary>
        /// <param name="n"></param>
        /// <param name="a"></param>
        /// <returns></returns>
        public int CountMaxRiseSubsequenceLength(int n,int[] a)
        {
            int res=1;
            dp = new int[a.Length + 1];
            dp[1] = 1;            
            for (int i = 2; i <= a.Length; i++)
            {
                int k = 0;
                for (int j=1;j<i;j++)
                {
                    if (a[j - 1] < a[i - 1]&&dp[k]<dp[j])
                        k = j;
                }
                dp[i] =Math.Max(1,dp[k] + 1);
                res = Math.Max(res,dp[i]);
            }
            return res;
        }
    }
}
